package algorithm.tree;

import algorithm.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断一棵树是否完全二叉树
 *
 * @author csp 2021-12-12
 */
public class Code03_CheckWholeTree {

    /*
        1）每一节点，有右孩子必须有左孩子
        2）右孩子为空时，左孩子不能有子节点



     */

    public static boolean isCBT(Node head) {
        if (head == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (
                    (leaf && (l != null || r != null))
                            ||
                            (l == null && r != null)
            ) {
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            if (l == null || r == null) {
                leaf = true;
            }

        }


        return true;
    }

}
